package leetcode_top;

import java.util.Stack;

public class Ex189 {
    class Solution1 {
        public void rotate(int[] nums, int k) {
            int len = nums.length;
            k %= len;
            if (k == 0) return;
            Stack<Integer> stack = new Stack<>();
            int idx = len - 1;
            for (int i = 0; i < k; i++) {
                stack.push(nums[idx--]);
            }
            idx = len - k - 1;
            while (idx >= 0) {
                nums[idx + k] = nums[idx];
                idx--;
            }
            while (!stack.isEmpty()) {
                nums[++idx] = stack.pop();
            }
        }
    }

    class Solution2 {
        public void rotate(int[] nums, int k) {
            int last, len = nums.length;
            if (k == len) return;
            for (int i = 0; i < k; i++) {
                last = nums[len - 1];
                for (int j = 1; j < len; j++) {
                    nums[j] = nums[j - 1];
                }
                nums[0] = last;
            }
        }
    }

    class Solution {
        public void rotate(int[] nums, int k) {
            int len = nums.length;
            k %= len;
            if (k == len) return;
            reverse(0, len - 1, nums);
            reverse(0, k - 1, nums);
            reverse(k, len - 1, nums);
        }

        public void reverse(int i, int j, int[] nums) {
            if (j < i) {
                reverse(i, j, nums);
                return;
            }
            while (i < j) {
                int t = nums[i];
                nums[i++] = nums[j];
                nums[j--] = t;
            }
        }
    }
}
